/// @tags: DP SegmentTree
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

constexpr LL MAXN = 1e5 + 3, SEGN = MAXN * 4, P = 1e9 + 9;

LL n, c;
int a[MAXN], b[MAXN];
int pos[MAXN], pcnt;
LL f[MAXN], g[MAXN][5], tp[MAXN];
LL t[SEGN], c1[SEGN], c2[SEGN], c3[SEGN];

inline int inc(int x, int y) {
  x += y;
  return x >= P ? x - P : x;
}

inline int dec(int x, int y) {
  x -= y;
  return x < 0 ? x + P : x;
}

inline void build(int q, int l, int r) {
  c1[q] = -1;
  c2[q] = 1;
  c3[q] = 0;
  if (l == r) {
    t[q] = f[l];
    return;
  }
  int mid = l + r >> 1;
  build(q << 1, l, mid);
  build(q << 1 | 1, mid + 1, r);
  t[q] = (t[q << 1] + t[q << 1 | 1]) % P;
}

inline void ud(LL x, int op, int q, int l, int r) {
  if (op == 1) {
    c1[q] = x;
    c2[q] = 1;
    c3[q] = 0;
    t[q] = x * (r - l + 1) % P;
  } else if (op == 2) {
    (c2[q] *= x) %= P;
    (c3[q] *= x) %= P;
    (t[q] *= x) %= P;
  } else {
    (c3[q] += x) %= P;
    (t[q] += x * (r - l + 1)) %= P;
  }
}

inline void ud(LL x, int op) { ud(x, op, 1, 1, c); }

inline void ps(int q, int l, int r) {
  int mid = l + r >> 1;
  if (c1[q] != -1) {
    ud(c1[q], 1, q << 1, l, mid);
    ud(c1[q], 1, q << 1 | 1, mid + 1, r);
    c1[q] = -1;
  }
  if (c2[q] != 1) {
    ud(c2[q], 2, q << 1, l, mid);
    ud(c2[q], 2, q << 1 | 1, mid + 1, r);
    c2[q] = 1;
  }
  if (c3[q]) {
    ud(c3[q], 3, q << 1, l, mid);
    ud(c3[q], 3, q << 1 | 1, mid + 1, r);
    c3[q] = 0;
  }
}

inline void modify(int ax, LL x, int op, int q, int l, int r) {
  if (l == r) {
    ud(x, op, q, l, r);
    return;
  }
  ps(q, l, r);
  int mid = l + r >> 1;
  if (mid >= ax)
    modify(ax, x, op, q << 1, l, mid);
  else
    modify(ax, x, op, q << 1 | 1, mid + 1, r);
  t[q] = (t[q << 1] + t[q << 1 | 1]) % P;
}

inline void modify(int ax, LL x, int op) { modify(ax, x, op, 1, 1, c); }

inline LL query(int x, int q, int l, int r) {
  if (l == r) return t[q];
  ps(q, l, r);
  int mid = l + r >> 1;
  if (mid >= x) return query(x, q << 1, l, mid);
  return query(x, q << 1 | 1, mid + 1, r);
}

inline LL query(int x) { return query(x, 1, 1, c); }

inline int main() {
  LL s, x, y;
  cin >> n >> c;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];
  for (int i = 1; i <= n; ++i) {
    if (a[i] || b[i]) pos[++pcnt] = i;
    if (a[i] && a[i] == b[i]) {
      cout << '0';
      return 0;
    }
    if ((a[i] && a[i] == a[i - 1]) || (b[i] && b[i] == b[i - 1])) {
      cout << '0';
      return 0;
    }
  }
  if (!pcnt) {
    LL ans = c * (c - 1) % P;
    for (int i = 2; i <= n; ++i) ans = ans * inc(c - 1, (c - 2) * (c - 2) % P) % P;
    cout << ans;
    return 0;
  }
  g[1][1] = g[1][3] = g[1][4] = 1;
  for (int i = 2; i <= n; ++i) {
    g[i][0] = (g[i - 1][1] + g[i - 1][3] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % P * (c - 3)) % P;
    g[i][1] = (g[i - 1][0] + g[i - 1][2] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % P * (c - 3)) % P;
    g[i][2] = (g[i - 1][1] + g[i - 1][2] * (c - 2) + g[i - 1][3] * (c - 2 + c - 3) +
               g[i - 1][4] * (c - 3) % P * (c - 3)) %
              P;
    g[i][3] = (g[i - 1][0] + g[i - 1][3] * (c - 2) + g[i - 1][2] * (c - 2 + c - 3) +
               g[i - 1][4] * (c - 3) % P * (c - 3)) %
              P;
    g[i][4] = (g[i - 1][0] + g[i - 1][1] + g[i - 1][2] * (c - 3) * 2 + g[i - 1][3] * (c - 3) * 2 +
               g[i - 1][4] * (c - 3 + (c - 4) * (c - 4) % P)) %
              P;
  }
  if (pos[1] == 1) {
    if (a[1] && b[1])
      f[b[1]] = 1;
    else if (a[1]) {
      for (int i = 1; i <= c; ++i)
        if (i != a[1]) f[i] = 1;
    } else {
      for (int i = 1; i <= c; ++i)
        if (i != b[1]) f[i] = 1;
    }
  } else {
    int u = pos[1];
    if (a[u] && b[u])
      f[b[u]] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 +
                 g[u - 1][4] * (c - 2) % P * (c - 3)) %
                P;
    else if (a[u]) {
      for (int i = 1; i <= c; ++i)
        if (i != a[u])
          f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 +
                  g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % P * (c - 3)) %
                 P;
    } else {
      for (int i = 1; i <= c; ++i)
        if (i != b[u])
          f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 +
                  g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % P * (c - 3)) %
                 P;
    }
  }
  build(1, 1, c);
  for (int i = 2, u, v, w, j; i <= pcnt; ++i) {
    w = pos[i] - pos[i - 1];
    s = t[1];
    if (a[pos[i]] && b[pos[i]]) {
      u = a[pos[i]];
      j = b[pos[i]];
      x = query(u);
      y = query(j);
      ud(0, 1);
      if (a[pos[i - 1]]) {
        v = a[pos[i - 1]];
        if (v == u)
          modify(j, (y * g[w][0] + (s - y + P) * g[w][2]) % P, 1);
        else if (v == j)
          modify(j, (x * g[w][1] + (s - x + P) * g[w][3]) % P, 1);
        else
          modify(j, (x * g[w][3] + y * g[w][2] + (s - x - y + P + P) * g[w][4]) % P, 1);
      } else {
        v = b[pos[i - 1]];
        if (v == u)
          modify(j, (y * g[w][1] + (s - y + P) * g[w][3]) % P, 1);
        else if (v == j)
          modify(j, (x * g[w][0] + (s - x + P) * g[w][2]) % P, 1);
        else
          modify(j, (x * g[w][2] + y * g[w][3] + (s - x - y + P + P) * g[w][4]) % P, 1);
      }
    } else if (a[pos[i]]) {
      u = a[pos[i]];
      x = query(u);
      if (a[pos[i - 1]]) {
        v = a[pos[i - 1]];
        if (v == u) {
          ud(g[w][0] - g[w][2] + P, 2);
          ud(s * g[w][2] % P, 3);
        } else {
          ud(g[w][2] - g[w][4] + P, 2);
          ud((x * g[w][3] + s * g[w][4] - x * g[w][4] % P + P) % P, 3);
          modify(v, (x * g[w][1] + (s - x + P) * g[w][3]) % P, 1);
        }
      } else {
        v = b[pos[i - 1]];
        if (v == u) {
          ud(g[w][1] - g[w][3] + P, 2);
          ud(s * g[w][3] % P, 3);
        } else {
          ud(g[w][3] - g[w][4] + P, 2);
          ud((x * g[w][2] + s * g[w][4] - x * g[w][4] % P + P) % P, 3);
          modify(v, (x * g[w][0] + (s - x + P) * g[w][2]) % P, 1);
        }
      }
      modify(u, 0, 1);
    } else {
      u = b[pos[i]];
      x = query(u);
      if (a[pos[i - 1]]) {
        v = a[pos[i - 1]];
        if (v == u) {
          ud(g[w][1] - g[w][3] + P, 2);
          ud(s * g[w][3] % P, 3);
        } else {
          ud(g[w][3] - g[w][4] + P, 2);
          ud((x * g[w][2] + s * g[w][4] - x * g[w][4] % P + P) % P, 3);
          modify(v, (x * g[w][0] + (s - x + P) * g[w][2]) % P, 1);
        }
      } else {
        v = b[pos[i - 1]];
        if (v == u) {
          ud(g[w][0] - g[w][2] + P, 2);
          ud(s * g[w][2] % P, 3);
        } else {
          ud(g[w][2] - g[w][4] + P, 2);
          ud((x * g[w][3] + s * g[w][4] - x * g[w][4] % P + P) % P, 3);
          modify(v, (x * g[w][1] + (s - x + P) * g[w][3]) % P, 1);
        }
      }
      modify(u, 0, 1);
    }
  }

  for (int i = 1; i <= c; ++i) f[i] = query(i);
  LL ans = 0;
  int u;
  if (pos[pcnt] == n)
    for (int i = 1; i <= c; ++i) ans = inc(ans, f[i]);
  else {
    u = n - pos[pcnt];
    for (int i = 1; i <= c; ++i)
      (ans += (g[u][0] + g[u][1] + g[u][2] * (c - 2) * 2 + g[u][3] * (c - 2) * 2 +
               g[u][4] * (c - 2) % P * (c - 3)) %
              P * f[i]) %= P;
  }
  cout << ((ans % P + P) % P);
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P5359 [SDOI2019] 染色.in", "r", stdin);
  freopen("P5359 [SDOI2019] 染色.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
